# Part of Cosmos by OpenGenus Foundation

# Python program to check if a given graph is Eulerian of not using eulerian path identification
#Complexity : O(V+E)
  
from collections import defaultdict

class Graph:
  
    def __init__(self,vertices):
        self.V= vertices #No. of vertices
        self.graph = defaultdict(list) # default dictionary to store graph
  
    # function to add an edge to graph
    def addEdge(self,u,v):
        self.graph[u].append(v)
        self.graph[v].append(u)
  
    #A function used by isConnected
    def DFSUtil(self,v,visited):
        # Mark the current node as visited 
        visited[v]= True
 
        #Recur for all the vertices adjacent to this vertex
        for i in self.graph[v]:
            if visited[i]==False:
                self.DFSUtil(i,visited)
  
    def isConnected(self):
  
        # Mark all the vertices as not visited
        visited =[False]*(self.V)
 
        #  Find a vertex with non-zero degree
        for i in range(self.V):
            if len(self.graph[i]) > 1:
                break
 
        # If there are no edges in the graph, return true
        if i == self.V-1:
            return True
 
        # Start DFS traversal from a vertex with non-zero degree
        self.DFSUtil(i,visited)
 
        # Check if all non-zero degree vertices are visited
        for i in range(self.V):
            if visited[i]==False and len(self.graph[i]) > 0:
                return False
         
        return True
 
 
    def isEulerian(self):
        # Check if all non-zero degree vertices are connected
        if self.isConnected() == False:
            return 0
        else:
            #Count vertices with odd degree
            odd = 0
            for i in range(self.V):
                if len(self.graph[i]) % 2 !=0:
                    odd +=1
            if odd == 0:
                return 2
            elif odd == 2:
                return 1
            elif odd > 2:
                return 0
 
 
    # Function to run test cases
    def test(self):
        res = self.isEulerian()
        if res == 0:
            print "graph is not Eulerian"
        elif res ==1 :
            print "graph has a Euler path"
        else:
            print "graph has a Euler cycle"
  
  
 
#Creating an example graph for implementation
g1 = Graph(5);
g1.addEdge(1, 0)
g1.addEdge(0, 2)
g1.addEdge(2, 1)
g1.addEdge(0, 3)
g1.addEdge(3, 4)
g1.test()
 
g2 = Graph(5)
g2.addEdge(1, 0)
g2.addEdge(0, 2)
g2.addEdge(2, 1)
g2.addEdge(0, 3)
g2.addEdge(3, 4)
g2.addEdge(4, 0)
g2.test();
 
g3 = Graph(5)
g3.addEdge(1, 0)
g3.addEdge(0, 2)
g3.addEdge(2, 1)
g3.addEdge(0, 3)
g3.addEdge(3, 4)
g3.addEdge(1, 3)
g3.test()
 

g4 = Graph(3)
g4.addEdge(0, 1)
g4.addEdge(1, 2)
g4.addEdge(2, 0)
g4.test()
 

g5 = Graph(3)
g5.test()